/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._779;

/**
 * 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 * <p>
 * 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
 * <p>
 * <p>
 * 例子:
 * <p>
 * 输入: N = 1, K = 1
 * 输出: 0
 * <p>
 * 输入: N = 2, K = 1
 * 输出: 0
 * <p>
 * 输入: N = 2, K = 2
 * 输出: 1
 * <p>
 * 输入: N = 4, K = 5
 * 输出: 1
 * <p>
 * 解释:
 * 第一行: 0
 * 第二行: 01
 * 第三行: 0110
 * 第四行: 01101001
 * <p>
 * 注意：
 * <p>
 * N 的范围 [1, 30].
 * K 的范围 [1, 2^(N-1)].
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._779
 * @ClassName: KGrammar
 * @Author: linyaonan
 * @Date: 2020/1/17 11:39
 */
public class KGrammar {


    public int kthGrammar(int N, int K) {
        if (N == 1 && K == 1) {
            return 0;
        }
        int i = kthGrammar(N - 1, K % 2 == 0 ? K / 2 : K / 2 + 1);
        if (i == 0 && K % 2 == 0) {
            return 1;
        }
        if (i == 0 && K % 2 == 1) {
            return 0;
        }
        if (i == 1 && K % 2 == 0) {
            return 0;
        }
        if (i == 1 && K % 2 == 1) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        KGrammar k = new KGrammar();
        // 30
        //434991989
        int i = 30;
        int z = 434991989;
        int p1 = k.kthGrammar(i, z);
        System.out.println(p1);

    }
}
